00100		This system, written by Doug Lenat, is our largest one, and is aimed
00200	at huge programs.  Although it has been massaged into writing a couple
00300	thirty-page programs, we want to emphasize that PUP5 is still merely an
00400	experimental vehicle, not a production environment. We shall mention the
00500	ideas it is based upon, analyze the amount of knowledge implemented 
00600	currently, provide a rationale for the chosen target domain, and compare its
00700	results with those of PUP1.
00800	
00900		All code is organized as an interacting community of small units,
01000	called beings.  Although complex, the structure of each being is the same:
01100	a set of answers to about thirty fixed questions. These questions represent
01200	everything you always wanted to know about a program. Neither the exact set
01300	chosen nor the number thirty is important; the magnitude of the list size is
01400	relevant to automatic programming, however.  Each being part is itself a
01500	little program which knows what the thirty questions are, and may ask any
01600	being any question it wants to.  Some being(s) must write the target code;
01700	we chose to have being X write all code similar to X.  For example, the SORT
01800	being contains a costly "big switch" hooked to various sorting algorithms,
01900	but the code it writes in any specific instance will be an efficient,
02000	single algorithm, tailor-written sort routine.  Although PUP5 insists on
02100	doing structured programming (hence uses something like macro expansion,)
02200	it employs feed forward, feedback, backtracking, and a contextual assertion
02300	base.  One bit of philosophy is that the system should defer making all
02400	decisions as long as possible.  We hope that by careful record-keeping and
02500	by this deferral we can eliminate most of the carelessness "bugs" that
02600	arise from brain hardware limitations. This is in contrast to PUP1,
02700	which views debugging as the predominant part of programming. Although PUP5
02800	is based around planning, it rarely believes it is finished when in fact it
02900	has overlooked some details.
03000	
03100	   We now present (most of) our tentative questions (being-parts):
03200	IDEN	How is this being referenced in English sentences?
03300	ARGS	Which are required and which are optional?
03400	ARG-CHECK  A predicate which examines each argument for suitability.
03500	EVAL-ARGS  Is the program an NLAMBDA? Is the code it writes Nλ?
03600	WHAT	A brief summary of this being: what it does. 
03700	WHY	A justification for this being's existence; why it is called.
03800	HOW	A summary of the method(s) used by the being to do its thing.
03900	EFFECTS What will be true after calling this being? Post-conditions.
04000	WHEN	Factors and weights telling how a propos the being is right now.
04100	META-CODE  The "body" of the code, but with uninstantiated subparts.
04200	COMMENTS   These help to fill in the META-CODE.
04300	REQUISITES What must be satisfied (actively) just before (pre-) the being
04400		executes? just after (post-) it executes? during execution (co-)?
04500	DEMONS	Which demons should be enabled during the being's execution?
04600	AFFECTS Which other beings might be called by this being?
04700	COMPLEXITY  A vector describing such features as recursiveness, overall
04800		cost, chance of failing, transparency to user, etc.
04900	SPECIALIZATIONS  What must we know to write a more streamlined version?
05000	ALTERNATIVES  If this doesn't work, what are some equivalent beings?
05100	GENERALIZATIONS  If even they don't work, what are some more general beings?
05200	PREDICATE  What type of values does this being return?
05300	DATA-STRUC   If it is one, how do we initialize, access, insert, delete?
05400	ENCODABLE  Describes the flow of control in writing a specialized new being.
05500	INHIBIT-CURRENT-DEMONS  A lock/unlock mechanism found necessary sometimes.
05600	FORM-CHANGING	Where in the being-tree can this being return to directly?
05700	
05800		The following chart summarizes the amount of knowledge which proved
05900	necessary to write a concept formation program (essentially the same as the
06000	one described in Winston's dissertation, but without any fancy graph-
06100	matching algorithm) and a gramatical inference program.  Both were about 8
06200	pages long when coded by a CS grad student, and about 30 pages long when 
06300	coded by PUP5.  The knowledge is of course embedded in beings, which is what
06400	the numbers in the following table represent.
06500	
06600	 type of         Used in    Used in    Used in    Created during    Total
06700	knowledge	  both      CF only    GI only    the  dialogue     beings
06800	
06900	Programming        50          10         7              40          107
07000	Domain-specific     4           9        11              12           36
07100	Total		   54          19        18              52          143
07200	
07300		Although each of these beings has about thirty answers, each of 
07400	which might contain several facts, only about ten facts from any given being
07500	are actually employed during the course of the program-writing dialogue.  A
07600	typical Programming being is OBTAIN-USABLE-INFORMATION. Its WHEN answer says
07700	that it is generally undesirable, but may be the only reasonable course to 
07800	follow if there exists new but not-yet-usable information somewhere. Its HOW
07900	answer says to Choose (non-deterministic, backtrack point) from these:
08000	translate, get totally new raw info, extract a small subset of existing raw
08100	info to concentrate upon, analyze implications of a small set of existing
08200	raw info.  A typical Domain-specific being is PARTITION-A-DOMAIN. Its
08300	SPECIALIZATIONS answer says to find out whether the partition is partial
08400	or total, whether it is weak or strong, and whether it is built by
08500	repeatedly accepting <element, classname> pairs and/or accepting an element
08600	(then guessing and verifying its classname) and/or accepting a classname 
08700	(then guessing and verifying its element(s)).
08800	
08900		Let us now comment on inductive inference programs as a target 
09000	domain.  The obvious apparent difficulty is the size of the programs: they
09100	are many pages long, whereas the typical AP target is a few lines long.
09200	But there are four big attractions:  (i) A wide range of complexity exists,
09300	from a one-page sequence extrapolater to META-DENDRAL.  (ii) Each more
09400	sophistocated system still uses many of the concepts of simpler inductive
09500	inference systems.  (iii) If a superhuman target is ever written, it could
09600	itself contribute to the field of automatic programming.  (iv) Since we
09700	are the "experts" in inductive inference ourselves, our use of intro-
09800	specition is as valid (and potentially as valuable) as Dendral's reliance
09900	upon experts' protocols.
10000	
10100		Lenat spent about 200 hours working through a hand simulation of
10200	the system, which helped solidify the set of beings needed. Another 800
10300	hours were spent implementing it in INTERLISP. Many popular AI language fea-
10400	tures were recoded and used (pattern-matching, assertions, goal-direction,
10500	apply teams, backtracking, special data types.)  PUP5 is a hundred pages
10600	long, and it is aimed at programs 100-10000 lines long. Notice that a brute
10700	force program-writer, or any one considering all interactions between all
10800	knowledge, would take an amount of time exponential in N to write a
10900	program of length N. Thus one measure of intelligence is ln(time)/length.
11000	For PUP5, writing the Concept Formation program, this value is 
11100	ln(3000 min) / 2500 lines  =  0.01 min/line.  Although this is thirty times
11200	better than PUP1, it is still much larger than practicality demands.  A
11300	second good measure of a program-writing system is the factor of system
11400	length divided by target program length.  PUP5 has a value of about
11500	100 pages / 34 pages  = 3,  compared to PUP1's value 20 pages / .1 page
11600	= 200.  Once again, PUP5 is far short of our goal value:  <<1 (i.e., a
11700	system which writes programs significantly longer than itself.)  Notice
11800	also that PUP5 has barely written two (dissimilar) programs, and that the
11900	times taken to do this are a thousandfold longer than PUP1's dialog time.
12000	
12100	The dialogue involved is carried on in a miniscule subset of English.  Since
12200	it encompasses precisely the sentences which the user wants to say (note:
12300	"the user" is NOT generic:  Lenat is the sole user so far!), the dialogue
12400	gives the illusion of being unconstrained. The way it works: each being re-
12500	cognizes and processes phrases referring to it. Often, PUP5 will simply ask
12600	a yes/no question, or a choice (where the user types back the numbers of the
12700	desired responses), so it is more meaningful to describe the length of the
12800	interaction in characters, not sentences or words.  PUP5 emits about 50000
12900	characters, and the user about 2000, during the course of the dialogue. The
13000	dialog uses five hours of CPU time, and another five real hours are taken by
13100	user read/think/respond time and swapout time. (Times refer to the PDP10
13200	TENEX system at SRI.)  Much of the interaction is unnecessary: PUP5 asks the
13300	user to name things which never are referenced again; this annoyance is now
13400	being worked on.
13500	
13600		During our reading and research, we have built up a list of 
13700	questions one should ask about any new automatic programming system.  Here
13800	is a partial list: Does it write one program?  How does the system size
13900	compare to the target program size?  What is the input dialog like?  What
14000	assumptions about and demands on the user does it contain?  How does the
14100	time taken for the system to write it compare with a human's time?  Does
14200	the system write a second, significantly different program?  How much of the
14300	system code is used in both dialogs, and how much is used in just writing
14400	one of them?  How does this reflect the similarity of the two target
14500	programs?  How much effort is required to extend the system to write a
14600	new program?  How is the system organized?  How is the target program
14700	organized, and how does it compare with a hand-written version wrt length,
14800	time, style?  What ideas (if any) does the system try to validate?  What
14900	mechanisms does it use to synthesize code?  If it does debugging, how?
15000	Can it modify its own programs? Others' programs?   Are the target programs
15100	really stored somewhere in the system? somewhere in the user?
15200	Unfortunately, all traces of humor depart when we ask these questions about
15300	most existing automatic programming systems.
15400	
15500		We have answered many of these questions about PUP5 in this brief
15600	description, and the remainder will be discussed in a forthcoming paper. A
15700	promising  sign of programming knowledge convergence is that out of 67 pro-
15800	gramming beings, 50 were used by PUP5 during the course of writing both of
15900	the target programs (concept formation and grammatical inference).  Future
16000	plans for PUP5 work include studying the various types of knowledge needed
16100	for programming, for inductive inference, and for specific target programs.
16200	This will be done by (hopefully) extending PUP5 to handle more and bigger
16300	tasks.